# 作者: 菅世博
# 2025年02月21日16时54分53秒
# 512326042@qq.com
class Node(object):
    """节点类"""

    def __init__(self, elem=-1, lchild=None, rchild=None):
        self.elem = elem
        self.lchild = lchild
        self.rchild = rchild


class Tree(object):
    """树类"""

    def __init__(self):
        self.root = None  # 根节点
        self.queue = []  # 辅助队列

    def add_node(self, elem):
        """添加节点"""
        new_node = Node(elem)
        self.queue.append(new_node)  # 将新节点加入队列
        # 判断树根是否为空
        if self.root is None:
            self.root = new_node
        else:
            if self.queue[0].lchild is None:  # 父亲的左孩子为空，新节点就作为左孩子
                self.queue[0].lchild = new_node
            else:  # 父亲的左孩子不为空，新节点就作为右孩子
                self.queue[0].rchild = new_node
                self.queue.pop(0)  # 将已经处理过的节点从队列中删除——出队

    def pre_order(self ,current_node:Node):
        """先序遍历"""
        if current_node:
            print(current_node.elem, end=' ')
            self.pre_order(current_node.lchild)
            self.pre_order(current_node.rchild)


if __name__ == '__main__':
    tree = Tree()
    for i in range(1, 11):
        tree.add_node(i)
    tree.pre_order(tree.root)
